package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 叶子相似的树872.java
 * @Description https://leetcode-cn.com/problems/leaf-similar-trees/
 * @createTime 2021年07月26日 19:12:00
 */
public class 叶子相似的树872 {

	public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
		//不能用层序遍历的方式，因为可能存在上层的节点没有叶子节点，然后放在了下层的前面
		/*List<Integer> list1 = bfs(root1);
		List<Integer> list2 = bfs(root2);*/

		//要用dfs的方式来进行处理
		List<Integer> list1 =new ArrayList<>();
		List<Integer> list2 = new ArrayList<>();
		dfs(root1,list1);
		dfs(root2,list2);
		return list1.equals(list2);
	}
	private static void dfs(TreeNode root,List<Integer> list) {
		if (root == null) {
			return;
		}
		if (root.left == null && root.right == null) {
			list.add(root.val);
			return;
		}
		if (root.left != null) {
			dfs(root.left,list);
		}
		if (root.right != null) {
			dfs(root.right,list);
		}
	}

	private static List<Integer> bfs(TreeNode root) {
		List<Integer> list = new ArrayList<>();
		if (root == null) {
			return list;
		}
		Deque<TreeNode> deque = new LinkedList<>();
		deque.offer(root);
		while (!deque.isEmpty()) {
			int size = deque.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = deque.poll();
				if (node == null) {
					continue;
				}
				if (node.left != null) {
					deque.offer(node.left);
				}
				if (node.right != null) {
					deque.offer(node.right);
				}
				if (node.left == null && node.right == null) {
					list.add(node.val);
				}
			}
		}
		return list;
	}


}
